{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#树 的嵌套列表法实现\n",
    "def BinaryTree(r):\n",
    "    return [r,[],[]]\n",
    "\n",
    "def insertLeft(root,newBranch):\n",
    "    t = root.pop(1)\n",
    "    if len(t) > 1:\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch,[],[]])\n",
    "\n",
    "def insertRight(root,newBranch):\n",
    "    t = root.pop(2)\n",
    "    if len(t) > 1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "    return root\n",
    "\n",
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "\n",
    "def setRootVal(root,newVal):\n",
    "    root[0] = newVal\n",
    "\n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, [4, [], []], []]\n",
      "[3, [9, [4, [], []], []], [7, [], [6, [], []]]]\n",
      "[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]\n",
      "[6, [], []]\n"
     ]
    }
   ],
   "source": [
    "r = BinaryTree(3)\n",
    "insertLeft(r,4)\n",
    "insertLeft(r,5)\n",
    "insertRight(r,6)\n",
    "insertRight(r,7)\n",
    "l = getLeftChild(r)\n",
    "print(l)\n",
    "setRootVal(l,9)\n",
    "print(r)\n",
    "insertLeft(l,11)\n",
    "print(r)\n",
    "print(getRightChild(getRightChild(r)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#节点链接法表示\n",
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "    \n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "    \n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "    \n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "    \n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "        \n",
    "    def getRootVal(self):\n",
    "        return self.key\n",
    "    \n",
    "    def preorder(self):\n",
    "        print(self.key)\n",
    "        if self.leftChild:\n",
    "            self.leftChild.preorder()\n",
    "        if self.rightChild:\n",
    "            self.rightChild.preorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "r = BinaryTree('a')\n",
    "r.insertLeft('b')\n",
    "r.insertRight('c')\n",
    "r.getRightChild().setRootVal('hello')\n",
    "r.getLeftChild().insertRight('d')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#树的应用：表达式解析 \n",
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def buildParseTree(fpexp):\n",
    "    fplist = fpexp.split()\n",
    "    pStack = Stack()\n",
    "    eTree = BinaryTree('')\n",
    "    pStack.push(eTree)\n",
    "    currentTree = eTree\n",
    "    for i in fplist:\n",
    "        if i == '(':\n",
    "            currentTree = insertLeft('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getLeftChild()\n",
    "        elif i not in ['+', '-', '*', '/', ')']:\n",
    "            currentTree.serRootVal(int(i))\n",
    "            parent = pStack.pop()\n",
    "            currentTree = parent\n",
    "        elif i in ['+', '-', '*', '/']:\n",
    "            currentTree.setRootVal(i)\n",
    "            currentTree.insertRight('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getRightChild()\n",
    "        elif i ==')':\n",
    "            currentTree = pStack.pop()\n",
    "        else:\n",
    "            raise ValueError\n",
    "    return eTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#表达式求值\n",
    "import operator\n",
    "def evaluate(parseTree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, \\\n",
    "             '*':operator.mul, '/':operator.truediv}\n",
    "    \n",
    "    leftC = parseTree.getLeftChild()\n",
    "    rightC = parseTree.getRightChild()\n",
    "    \n",
    "    if leftC and rightC:\n",
    "        fn = opers[parseTree.getRootVal()]\n",
    "        return fn(evaluate(leftC),evaluate(rightC))\n",
    "    else:\n",
    "        return parseTree.getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#树的遍历\n",
    "def preorder(tree):\n",
    "    if tree:\n",
    "        print(tree.getRootVal())\n",
    "        preorder(tree.getLeftChild())\n",
    "        preorder(tree.getRightChild())\n",
    "\n",
    "def postorder(tree):\n",
    "    if tree != None:\n",
    "        postorder(tree.getLeftChild())\n",
    "        postorder(tree.getRightChild())\n",
    "        print(tree.getRootVal())\n",
    "        \n",
    "def inorder(tree):\n",
    "    if tree != None:\n",
    "        inorder(tree.getLeftChild())\n",
    "        print(tree.getRootVal())\n",
    "        inorder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#表达式求值后序遍历\n",
    "def postordereval(tree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, \\\n",
    "             '*':operator.mul, '/':operator.truediv}\n",
    "    res1 = None\n",
    "    res2 = None\n",
    "    if tree:\n",
    "        res1 = postordereval(tree.getLeftChild())\n",
    "        res2 = postordereval(tree.getRightChild())\n",
    "        if res1 and res2:\n",
    "            return opers[tree.getRootVal()](res1,res2)\n",
    "        else:\n",
    "            return tree.getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#中序遍历生成表达式\n",
    "def printexp(tree):\n",
    "    sVal = ''\n",
    "    if tree:\n",
    "        sVal = '(' + printexp(tree.getLeftChild())\n",
    "        sVal = sVal + str(tree.getRootVal())\n",
    "        sVal = sVal + printexp(tree.getRightChild())+')'\n",
    "    return sVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "    \n",
    "    def insert(self,k):\n",
    "        self.heapList.append(k)\n",
    "        self.currentSize = self.currentSize + 1\n",
    "        self.percUp(self.currentSize)\n",
    "    \n",
    "    def percUp(self,i):\n",
    "        while i //2 > 0 :\n",
    "            if self.heapList[i] < self.heapList[i//2]:\n",
    "                tmp = self.heapList[i//2]\n",
    "                self.heapList[i //2 ] = self.heapList[i]\n",
    "                self.heapList[i] = tmp\n",
    "            i = i // 2\n",
    "    \n",
    "    def delMin(self):\n",
    "        retval = self.heapList[1]  #移走堆顶\n",
    "        self.heapList[1] = self.heapList[self.currentSize]\n",
    "        self.currentSize = self.currentSize - 1\n",
    "        self.heapList.pop()\n",
    "        self.percDown(1)             #新顶下沉\n",
    "        return retval\n",
    "        \n",
    "    def percDown(self,i):\n",
    "        while (i * 2) <= self.currentSize:\n",
    "            mc = self.minChild(i)\n",
    "            if self.heapList[i] > self.heapList[mc]:\n",
    "                tmp = self.heapList[i]\n",
    "                self.heapList[i] = self.heapList[mc]\n",
    "                self.heapList[mc] = tmp\n",
    "            i = mc\n",
    "    \n",
    "    def minChild(self,i):\n",
    "        if i * 2 + 1 >self.currentSize:\n",
    "            return i * 2                #唯一的子节点\n",
    "        else:\n",
    "            if self.heapList[i * 2] < self.heapList [i * 2 + 1]:\n",
    "                return i * 2\n",
    "            else:\n",
    "                return i * 2 + 1\n",
    "    \n",
    "    def buildHeap(self,alist):\n",
    "        i  = len(alist) // 2      #从最后节点的父节点开始下沉，因为叶节点无需下沉\n",
    "        self.currentSize = len(alist)\n",
    "        self.heapList = [0] + alist[:]\n",
    "        print(len(self.heapList),i)\n",
    "        while (i > 0):\n",
    "            print(self.heapList,i)\n",
    "            self.percDown(i)\n",
    "            i = i - 1\n",
    "            print(self.heapList,i)\n",
    "            \n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "#二叉查找树      需要用到BST和TreeNode两个类\n",
    "class BinarySearchTree:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "    \n",
    "    def length(self):\n",
    "        return self.size\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self.root.__iter__()\n",
    "    \n",
    "    def put(self,key,val):\n",
    "        if self.root:\n",
    "            self._put(key,val,self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(key,val)\n",
    "        self.size = sele.size + 1\n",
    "        \n",
    "    def _put(self,key,val,currentNode):\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "        \n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "        \n",
    "    def __setitem__(self,k,v):\n",
    "        self.put(k,v)\n",
    "    \n",
    "    def get(self,key):\n",
    "        if self.root:\n",
    "            res = self._get(key,self.root)\n",
    "            if res:\n",
    "                return res.payload\n",
    "            else:\n",
    "                return None\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    def _get(self,key,currentNode):\n",
    "        if not currentNode:\n",
    "            return None\n",
    "        elif currentNode.key == key:\n",
    "            return currentNode\n",
    "        elif key < currentNode.key:\n",
    "            return self._get(key,currentNode.leftChild)\n",
    "        else:\n",
    "            return self._get(key,currentNode.rightChild)\n",
    "        \n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "    \n",
    "    def __contains__(self,key):\n",
    "        if self._get(key,self.root):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def delete(self,key):\n",
    "        if self.size > 1:\n",
    "            nodeToRemove = self._get(key,self.root)\n",
    "            if nodeToRemove:\n",
    "                self.remove(nodeToRemove)\n",
    "                self.size = self.size - 1\n",
    "            else:\n",
    "                raise KeyError('Error, key not in tree')\n",
    "        elif self.size == 1 and self.root.key == key:\n",
    "                self.root = None\n",
    "                self.size = self.size - 1\n",
    "        else:\n",
    "            raise KeyError('Error, key not in tree')\n",
    "        \n",
    "    def __delitem__(self,key):\n",
    "        self.delete(key)\n",
    "    \n",
    "    def remove(self,currentNode):\n",
    "        if currentNode.isLeaf():                #没有子节点，直接删除\n",
    "            if currentNode == currentNode.parent.leftChild:\n",
    "                currentNode.parent.leftChild = None\n",
    "            else:\n",
    "                currentNode.parent.rigthChild = None\n",
    "                \n",
    "        elif currentNode.hasBothChildren():    #节点有两个子节点\n",
    "            succ = currentNode.findSuccessor()\n",
    "            succ.spliceOut()\n",
    "            currentNode.key = succ.key\n",
    "            currentNode.payload = succ.payload\n",
    "            \n",
    "        else:\n",
    "            if currentNode.hasLeftChild():              #节点本身有左子节点\n",
    "                if currentNode.isLeftChild():           #节点是父节点的左子节点\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.leftChild\n",
    "                elif currentNode.isRightChild():        #节点是父节点的右子节点\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.rightChild\n",
    "                else:                                   #节点是根节点\n",
    "                    currentNode.replaceNodeData(currentNode.leftChild,\n",
    "                                               currentNode.leftChild.payload,\n",
    "                                               currentNode.leftChild.leftChild,\n",
    "                                               currentNode.leftChild.rightChild)\n",
    "            else:           #节点有右子节点\n",
    "                if currentNode.isLeftChild():           #节点是父节点的左子节点\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.leftChild\n",
    "                elif currentNode.isRightChild():        #节点是父节点的右子节点\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.rightChild\n",
    "                else:                                   #节点是根节点\n",
    "                    currentNode.replaceNodeData(currentNode.rightChild,\n",
    "                                               currentNode.rightChild.payload,\n",
    "                                               currentNode.rightChild.leftChild,\n",
    "                                               currentNode.rightChild.rightChild)\n",
    "\n",
    "                \n",
    "        \n",
    "                               \n",
    "class TreeNode:\n",
    "    def __init__(self,key,val,left=None,right=None,parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "    \n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "    \n",
    "    def hasRightChild(self):\n",
    "        return self.rigthChild\n",
    "    \n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "    \n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "    \n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "    \n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "    \n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "    \n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "    \n",
    "    def replaceNodeData(self,key,val,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self\n",
    "    \n",
    "    def __iter__(self):\n",
    "        if self:\n",
    "            if self.hasLeftChild():\n",
    "                for elem in self.leftChild:\n",
    "                    yield elem\n",
    "            yield self.key\n",
    "            if self.hasRightChild():\n",
    "                for elem in self.rightChild:\n",
    "                    yield elem\n",
    "    def findSuccessor(self):\n",
    "        succ = None\n",
    "        if self.hasRightChild():\n",
    "            succ = self.rightChild.findMin()\n",
    "        else:                #目前不会遇到\n",
    "            if self.parent:\n",
    "                if self.isLeftChild():\n",
    "                    succ = self.parent\n",
    "                else:\n",
    "                    self.parent.rightChild = None\n",
    "                    succ = self.parent.findSuccessor()\n",
    "                    self.parent.rightChild = self\n",
    "        return succ\n",
    "    \n",
    "    def findMin(self):                #找到左下角 \n",
    "        current = self\n",
    "        while current.hasLeftChild():\n",
    "            current = current.leftChild\n",
    "        return current\n",
    "    \n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():\n",
    "            if self.isLeftChild():\n",
    "                self.parent.leftChild = None\n",
    "            else:\n",
    "                self.parent.rightChild = None\n",
    "        elif self.hasAnyChildren():\n",
    "            if self.hasLeftChild():     #目前不会遇到\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.leftChild = self.leftChild\n",
    "                else:\n",
    "                    self.parent.rightChild = self.leftChild\n",
    "                self.leftChild.parent = self.parent\n",
    "            else:                #摘除右子节点\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.leftChild = self.rightChild\n",
    "                else:\n",
    "                    self.parent.rightChild = slef.rightChild\n",
    "                self.rightChild.parent = self.parent\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "#AVL树   重新定义_put\n",
    "class AVLTree:\n",
    "        \n",
    "    def _put(self,key,val,currentNode):\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "                slef.updataBalance(currentNode.leftChild)              #加了调整因子\n",
    "        \n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "                self.updateBalance(currentNode.rightChild)             #添加了调整因子\n",
    "        \n",
    "    def updateBalance(self,node):\n",
    "        if node.balanceFactor > 1 or node.balanceFactor < -1:\n",
    "            self.rebalance(node)\n",
    "            return\n",
    "        if node.parent != None:\n",
    "            if node.isLeftChild():\n",
    "                node.parent.balanceFactor += 1\n",
    "            elif node.isRightChild():\n",
    "                node.parent.banalceFactor -= 1\n",
    "            if node.parent.balanceFactor != 0:\n",
    "                self.updateBalance(node.parent)\n",
    "    def rotateLeft(self,rotRoot):\n",
    "        pass\n",
    "    def rotateRight(self,rotRoot):\n",
    "        pass"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "faker",
   "language": "python",
   "name": "faker"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
